\documentclass{article}
\newtheorem{definition}{Definition}{}

\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsmath}

\begin{document}
All counterexamples use word count.

\noindent \begin{definition}[Known Ordering]\label{def:knownorder}
$\exists$ some known function $f\left(k_{1},k_{2}\right)$ for keys
$k_{1} \neq k_{2}$ which is transitive and returns
$TRUE$ iff $k_{1} \leq k_{2}$.
\end{definition}

English Translation: We know the ordering function.

Counter Example: If the input uses a hashmap (as would make sense) with
string:key mappings, the ordering of a traversal of the list of entries is not a
lexical ordering of the keys, but a numerical ordering of the hashes of
the keys (at least in Java). The programmer must realize and account for this,
which means an understanding of the data structures.

\noindent \begin{definition}[Consistent Ordering]\label{def:consistentorder}
$\forall$ keys $k_{1}, k_{2}$ such that $k_{1}$ precedes $k_{2}$ in ordered
list $c_{i}$ used as input for aggregation function
$A\left(c_{0},\ldots,c_{d}\right)$ $\Rightarrow$ $f\left(k_{1},k_{2}\right)$.
\end{definition}

English Translation: The same ordering function is used in all incoming lists. 

Counter Example: One list could be derived from a hashmap, ordered on the hashes
of the keys. A second list may have been processed to and follow lexical
ordering of the keys. A third may be sorted on the number of occurrences of each
string.

\noindent \begin{definition}[Chunk Self Sufficiency]\label{def:chunksufficiency}
In aggregation function $A\left(c_{0},\ldots,c_{d}\right)$, list $c_{i}$ can be
decomposed into concatenated lists $c_{i}^{0} \cdot c_{i}^{1} \cdot c_{i}^{2}$
and $c_{j}$ into $c_{j}^{0} \cdot c_{j}^{1} \cdot c_{j}^{2}$ for $i\neq j$. If
for output $c_{a}$ derived from chunks $c_{i}^{1}$ and $c_{j}^{1}$ $\exists$
keys $k_{1},k_{2}\subset$ output $c_{a}^{1}$ such that
$f\left(k_{1},k_{2}\right)$, then $k_{1},k_{2} \subset$ output $c_{a}$ of
$A\left(c_{0},\ldots,c_{d}\right)$  $\Rightarrow$ $f\left(k_{1},k_{2}\right)$.
\end{definition}

English Translation: The order of the output derived from two chunks cannot be
changed by the addition of different chunks within the same streams.

Counter Example: If the output is ordered on the number of occurrences of each
string, but string $a$ occurs in $c_{i}^{1}$ and $c_{j}^{2}$, the value used in
the ordering of $a$, and thus the ordering of $a$ relative to other elements,
can change when $c_{j}^{2}$ is aggregated with the output from the original
aggregation.

This might need to be made stronger. We might have to say the value cannot
change (in order to allow full streaming). That would be enforced through when
chunks can be used.
\end{document}